#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <set>
using namespace std;
class Solution
{
public:
    // f(n) 表示从a[0]到a[n]中,取a[n],最长上升子序列的长度
    // f(n) = max f(i) + 1 其中0<=i<n 且 a[i] < a[n]
    // cnt(n)表示 a[0]到a[n]中,取a[n],最长上升子序列的个数
    //参考题解:https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/solution/dong-tai-gui-hua-dong-tu-fu-zhu-li-jie-ru-you-bang/
    int findNumberOfLIS(vector<int> &nums)
    {
        vector<int> f(nums.size(), 0);
        vector<int> cnt(nums.size(), 1);
        int maxval = 0, maxlen = 0;
        for (int n = 0; n < nums.size(); ++n)
        {
            for (int i = 0; i < n; ++i)
            {
                if (nums[i] < nums[n])
                {
                    if (f[i] + 1 > f[n])
                    {
                        f[n] = f[i] + 1;
                        cnt[n] = cnt[i];
                    }
                    else if (f[i] + 1 == f[n])
                        cnt[n] += cnt[i];
                }
            }
            maxlen = max(maxlen, f[n]);
        }
        for (int i = 0; i < f.size(); ++i)
        {
            if (f[i] == maxlen)
                maxval += cnt[i];
        }
        return maxval;
    }
};